/**
 * 给定一个循环数组nums（nums[nums.length - 1]的下一个元素是nums[0]），返回nums中每个元素的 下一个更大元素 。
 *
 * 数字 x的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/next-greater-element-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class NextGreaterElements {
    public int[] nextGreaterElements(int[] nums) {
        int n=nums.length;
        Stack<Integer> stack=new Stack<>();
        int[] ret=new int[n];
        for(int i=2*n-1;i>=0;i--) {
            while(!stack.isEmpty()&&stack.peek()<=nums[i%n]) {
                stack.pop();
            }
            ret[i%n]= stack.isEmpty() ? -1 :stack.peek();
            stack.push(nums[i%n]);
        }
        return ret;
    }
}